package com.captain.special.二叉树.简单;
import com.captain.leetcode.TreeNode;
import java.util.*;
/**
 * Des:
 * TODO 对于搜索二叉树而言,中序遍历就是一个排序好的数组
 *
 * @author XL
 * @Date 2022/5/7 9:09
 */
public class 二叉搜索树中的众数501 {
    List<Integer> answer = new ArrayList<Integer>();
    int base, count, maxCount;

    public int[] findMode(TreeNode root) {
        recur(root);
        int[] arr = new int[answer.size()];
        for (int i = 0; i < answer.size(); i++) {
            arr[i] = answer.get(i);
        }
        return arr;
    }

    public void recur(TreeNode node) {
        if (node == null) {
            return;
        }
        //中序遍历
        recur(node.left);
        //维护变量
        maintain(node.val);
        recur(node.right);
    }

    public void maintain(int val) {
        if (base == val) {
            count++;
        } else {
            base = val;
            count = 1;
        }
        if (count == maxCount) {
            answer.add(val);
        }
        if (count > maxCount) {
            maxCount = count;
            answer.clear();
            answer.add(val);
        }
    }
}
